package com.nowcoder.Offer.Tree;

import java.util.HashMap;

/**
 * 通过二叉树的前序遍历 中序遍历 重构二叉树
 */
public class RebuildTree {

    HashMap<Integer,Integer> dic = new HashMap<>();

    int[] po ;

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        po = pre;
        for(int i=0; i<in.length; i++){
            //put the inorder index in the dic
            dic.put(in[i] , i);
        }
        return rebuild(0,0,pre.length-1);
    }

    public TreeNode rebuild(int pre_root, int in_left, int in_right){
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(po[pre_root]);

        int index = dic.get(po[pre_root]);

        root.left = rebuild(pre_root + 1, in_left, index - 1);

        root.right = rebuild(pre_root + 1 + (index - in_left) ,
                index + 1, in_right);

        return root;
    }
}
